星尘

LeetCode - 704. 二分查找

发表于 更新于 分类于

704. 二分查找

题目

题目链接：https://leetcode-cn.com/problems/binary-search/

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:  # 当left==right，区间[left, right]依然有效，所以用 <=
            middle = left + (right - left) // 2  # 防止 (right + left) 超出最大值溢出
            if nums[middle] > target:
                right = middle - 1  # while 里面已经包含等于的关系了，所以这里要 -1 
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle

        return -1


if __name__ == '__main__':
    solution = Solution()
    print(solution.search(nums=[-1,0,3,5,9,12], target=2))

变体

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:  # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            middle = left + (right - left) // 2 
            if nums[middle] > target:
                right = middle  # 这里不减 1，因为是左闭右开区间，在[left, middle)中
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle

        return -1


if __name__ == '__main__':
    solution = Solution()
    print(solution.search(nums=[-1,0,3,5,9,12], target=2))

总结

如果给定的数组是左闭右闭的，那么 while 的判断条件是 left <= right。如果 nums[middle] > target 时，right = middle - 1。

如果给定的数组是左闭右开的，那么 while 的判断条件是 left < right。如果 nums[middle] > target 时，right = middle。

参考

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md#704-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE